/**
 * https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/submissions/585338157/
 * 剑指 Offer 13. 机器人的运动范围
 * medium 陈贝纯 2024.12.06
 * bfs
 */

class Solution {
public:
    int calculate(int x){
        int res=0;
        while(x){
            res+=x%10;
            x/=10;
        }
        return res;
    }
    int wardrobeFinishing(int m, int n, int cnt) {
        queue<pair<int,int>> q;
        q.push({0,0});
        int dx[2]={0,1};
        int dy[2]={1,0};
        vector<vector<bool>> vist(m,vector<bool>(n,false));
        vist[0][0]=true;
        int ans=1;
        while(!q.empty()){
            auto [x,y]=q.front();
            q.pop();
            for(int i=0;i<2;++i){
                int repx=x+dx[i];
                int repy=y+dy[i];
                if(repx<0||repx>=m||repy<0||repy>=n||vist[repx][repy]||calculate(repx)+calculate(repy)>cnt)
                continue;
                vist[repx][repy]=true;
                q.push({repx,repy});
                ans++;
            }
        }
        return ans;
    }
};